Премештаљка има облик матрице од \(V\) врста и \(K\) колона. Једно поље премештаљке је празно, а на осталим местима су плочице са бројевима од 1 до \(m \cdot n - 1\). Плочица поред празне позиције може са њом да замени место. Померање неке плочице на лево, на десно, навише, односно наниже означаваћемо редом са L, D, V, N.

За дате димензије матрице, почетни распоред бројева (празнина је означена нулом) и низ потеза претстављен словима L, D, V, N, приказати распоред бројева након овог низа потеза.

Улаз

У првом реду стандардног улаза налазе се бројеви \(V\) и \(K\), димензије матрице (\(2 \leq V \leq 10\), \(2 \leq V \leq 10\)). У наредних \(K\) редова налази се низ од \(V\) бројева из опсега \([0, m \cdot n - 1]\) раздвојених по једним ртазмаком, тако да се сваки од тих бројева појављује по једном у матрици. Након тога, у последњем реду је ниска слова из скупа \(\{L, D, V, N\}\), дужине не веће од 20.

Подаци су такви да је премештања увек могуће извести.

Излаз

У \(V\) редова исписати редом врсте матрице бројева која се добија када се на датој матрици изведу премештања задата ниском слова.

Пример

Улаз

3 4
1 2 3 4
5 6 7 8
9 10 11 0
DNDVL

Излаз

1 2 3 4
5 10 6 8
9 7 0 11